You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.
You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Example 1:
Input: sticks = [2,4,3] Output: 14 Explanation: You start with sticks = [2,4,3]. 1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4]. 2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9]. There is only one stick left, so you are done. The total cost is 5 + 9 = 14.
Example 2:
Input: sticks = [1,8,3,5] Output: 30 Explanation: You start with sticks = [1,8,3,5]. 1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5]. 2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8]. 3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17]. There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.
Example 3:
Input: sticks = [5] Output: 0 Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.
Constraints:
1 <= sticks.length <= 1041 <= sticks[i] <= 104
Average Rating: 4.89 (35 votes)
Video Solution
Solution Article
Approach 1: Greedy
Intuition and Algorithm
Always pick two of the smallest sticks to connect and continue doing this until you get only one stick. Let's see why this works.
Consider 4 sticks of the following lengths:
sticks=[a1,a2,a3,a4]
Let's try to connect them left to right.
After first merge, we will have:
sticks=[(a1+a2),a3,a4],cost=(a1+a2)
After second merge, we will have:
sticks=[(a1+a2+a3),a4],cost=(a1+a2)+(a1+a2+a3)
And finally, last stick will look like:
sticks=[(a1+a2+a3+a4)],cost=(a1+a2)+(a1+a2+a3)+(a1+a2+a3+a4)
The final cost can be re-written as: cost=(3a1+3a2+2a3+a4)
As we can see, the sticks which are connected first are included in the final cost more than the ones that are picked later. Hence, it is optimal to pick smaller sticks first to get the smallest cost.
Let's try to figure out which data structure will be optimal to perform following tasks:
- Get two of the smallest sticks (
stick1andstick2) from the array. - Add one stick (
stick1 + stick2) back to the array.
We can use a min heap data structure (which is, generally, implemented as a PriorityQueue in most languages) which gives us O(logN) complexity for both the operations.
Complexity Analysis
-
Time complexity : O(NlogN), where N is the length of the input array. Let's break it down:
-
Step 1) Adding N elements to the priority queue will be O(NlogN).
-
Step 2) We remove two of the smallest elements and then add one element to the priority queue until we are left with one element. Since each such operation will reduce one element from the priority queue, we will perform N−1 such operations. Now, we know that both
addandremoveoperations take O(logN) in priority queue, therefore, complexity of this step will be O(NlogN).
-
-
Space complexity : O(N) since we will store N elements in our priority queue.
October 15, 2020 11:23 AM
The quality of these articles are getting better and better. Very well written!
this is basically the algo for building a huffman coding tree
Can someone explain to me why this won't work?
class Solution {
public int connectSticks(int[] sticks) {
// just sort the array
Arrays.sort(sticks);
// current value is current + previous
for (int i = 1; i < sticks.length; i++) {
sticks[i] = sticks[i] + sticks[i -1];
}
// get the sum of all but first index
int cost = 0;
for (int i = 1; i < sticks.length; i++) {
cost += sticks[i];
}
return cost;
}
}
Understanding how heaps and priority queues work is so important!
May 29, 2021 12:48 PM
Nit : The solution mentions 'Approach 1: Greedy' which might make one think there is another approach described. there not :-)
October 29, 2020 1:09 PM
well written compared to other solutions
I think the time complexity for constructing a PriorityQueue should be O(N), and inserting into PriorityQueue should be O(NlogN):
https://stackoverflow.com/a/34697891
I really struggled on this until I realized I can "re-use" sticks already formed. Kept thinking it needed to append to existing stick. Once I realized that it was heap time!
Damn. Sucks I didnt come up with this, seems pretty straightforward after seeing solution :(
I tried solving it like the following but it doesn't work. I don't understand why?
public int connectSticks(int[] sticks) {
if(sticks == null || sticks.length == 0)
return 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int stick : sticks) {
minHeap.offer(stick);
}
int prevCost = 0;
int currentCost = minHeap.poll();
while(!minHeap.isEmpty()) {
int stick = minHeap.poll();
currentCost += stick;
prevCost += currentCost;
}
return prevCost;
}Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/29/2021 19:00 | Accepted | 112 ms | 24.2 MB | cpp |
xxxxxxxxxxclass Solution {public: int connectSticks(vector<int>& sticks) { priority_queue<int, vector<int>, greater<int>>pq; for(int i=0;i<sticks.size();i++) pq.push(sticks[i]); int cost = 0; while(pq.size()>1) { int first = pq.top(); pq.pop(); int second = pq.top(); pq.pop(); cost += (first+second); pq.push(first+second); } return cost; }};